\documentclass[submission]{FPSAC2017}
\usepackage{enumerate}
\usepackage{amscd}
\usepackage{tikz}

\articlenumber{85}
\addbibresource{85_Pawlowski.bib}


\newtheorem{thm}{Theorem}[section]
\newtheorem*{thm*}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\theoremstyle{definition} \newtheorem{defn}[thm]{Definition}
\theoremstyle{definition} \newtheorem*{defn*}{Definition}
\theoremstyle{definition} \newtheorem{ex}[thm]{Example}
\newtheorem*{lem*}{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem*{cor*}{Corollary}
\theoremstyle{definition} \newtheorem{rem}[thm]{Remark}
\newtheorem*{warn}{Warning}
\newtheorem*{conj*}{Conjecture}
\newtheorem{conj}{Conjecture}
\newtheorem{obs}{Observation}
\newtheorem{question}{Question}
\newtheorem{prop}[thm]{Proposition}

\crefname{lem}{Lemma}{Lemmas}

\newcommand{\CC}{\mathbb{C}}
\newcommand{\Cyl}{\mathcal{C}}
\newcommand{\Tor}{\mathcal{T}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\Cor}{\mathcal{K}}
\newcommand{\Sym}{\operatorname{Sym}}

\newcommand{\sq}{{\scriptstyle \square}}
\newcommand{\Red}{\mathcal{R}}
\newcommand{\affS}{\widetilde{S}}
\newcommand{\affF}{\widetilde{F}}
\newcommand{\fS}{\mathfrak{S}}
\renewcommand{\SS}{\mathbb{S}}

\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\Asc}{Asc}
\DeclareMathOperator{\QSym}{QSym}
\DeclareMathOperator{\shape}{shape}
\DeclareMathOperator{\remd}{rem}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Bound}{Bound}
\DeclareMathOperator{\trunc}{trunc}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\Ind}{Ind}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\BCov}{BCov}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\av}{av}
\DeclareMathOperator{\BPhi}{B\Phi}
\DeclareMathOperator{\Rch}{Rch}
\DeclareMathOperator{\lex}{lex}
\DeclareMathOperator{\stb}{stb}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\vspan}{span}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Fl}{Fl}
\DeclareMathOperator{\id}{id}

\renewcommand{\det}{\operatorname{det}}

\newcommand{\trncotimes}{\widehat\otimes}
\DeclareMathOperator{\trch}{\overline{ch}}




\usepackage{lipsum}

\title{A representation-theoretic interpretation of positroid classes}

\author{Brendan Pawlowski}

\address{Department of Mathematics, University of Michigan\\}

\received{\today}

\abstract{A positroid variety is the set of points in a complex Grassmannian whose matroid is a fixed positroid, in the sense of Postnikov. A positroid class is then the cohomology class of a positroid variety. We define a family of representations of general linear groups whose characters are the Schur-positive symmetric functions corresponding to positroid classes. This gives a new algebraic interpretation of Schubert times Schur structure coefficients, as well as the three-point Gromov-Witten invariants for Grassmannians, proving a conjecture of Postnikov. As a byproduct we obtain an effective recursion for decomposing positroid classes into Schubert classes.}

\resume{Une vari\'et\'e positro\"ide est un ensemble de points dans un Grassmannien complexe dont le matro\"ide est un positro\"ide fixe, dans le sens de Postnikov. Une classe positro\"ide est alors la classe de cohomologie d'une vari\'et\'e positro\"ide. On d\'efinit une famille de repr\'esentations de groupes g\'en\'eraux lin\'eaires dont les caract\`eres sont les fonctions Schur-positives symm\'etriques correspondant aux classes positro\"ides. Cela donne une nouvelle interpr\'etation alg\'ebrique au coefficients de structure Schubert fois Schur, ainsi qu'aux invariants \`a trois points de Gromov-Witten pour les Grassmanniens, prouvant une conjecture de Postnikov. Comme cons\'equence, on obtient une r\'ecursion effective pour d\'ecomposer les classes positro\"ides en classes de Schubert.}


\begin{document}

\maketitle

\section{Introduction}

Let $\Gr_K(k,n)$ denote the Grassmannian of $k$-planes in $K^n$ for a field $K$, or simply $\Gr(k,n)$ in the case $K = \CC$. The \emph{matroid} of $V \in \Gr_K(k,n)$ is the set of $k$-subsets $I \subseteq [n] := \{1, 2, \ldots, n\}$ such that some (any) matrix whose rowspan is $V$ has nonzero maximal minor in columns $I$.
\begin{defn}
The \emph{totally nonnegative Grassmannian} $\Gr_{\RR}(k,n)^+$ is the set of $k$-planes $V = \operatorname{rowspan}(A)$ where all the maximal minors of $A$ are nonnegative. A \emph{positroid} is the matroid of a member of $\Gr_{\RR}(k,n)^+$.
\end{defn}

Postnikov \cite{postnikov-positroids} gave several combinatorial objects which are in bijection with positroids, and used them to describe the locus of points in $\Gr_{\RR}(k,n)^+$ whose matroid is a fixed positroid. Knutson, Lam, and Speyer \cite{positroidjuggling} studied the following complex analogue of Postnikov's positroid cells.

\begin{defn}
The \emph{positroid variety} $\Pi_M \subseteq \Gr(k,n)$ of a positroid $M \subseteq {[n] \choose k}$ is the Zariski closure of the set of $k$-planes with matroid $M$.
\end{defn}

Let $\Lambda(k)$ denote the ring of symmetric polynomials $\ZZ[x_1, \ldots, x_k]^{S_k}$, and $\Lambda^{n-k}(k)$ the quotient by the ideal generated by the homogeneous symmetric polynomials $h_d(X_k)$ for $d > n-k$. The ring $\Lambda^{n-k}(k)$ is isomorphic to the integral cohomology ring of the Grassmannian $\Gr(k, n)$ of $k$-planes in $\CC^n$, and under this isomorphism the cone of cohomology classes Poincar\'e dual to subvarieties of $\Gr(k, n)$ corresponds to the cone of Schur-positive elements in $\Lambda^{n-k}(k)$ \cite{youngtableaux}. 

\begin{defn}
For a positroid $M \subseteq {[n] \choose k}$, let $G_M \in \Lambda^{n-k}(k)$ represent the cohomology class of the positroid variety $\Pi_M$.
\end{defn}
The Schur-positive elements $G_M \in \Lambda^{n-k}(k)$ are the central objects of this paper. Via taking characters, the Grothendieck ring of finite-dimensional complex polynomial representations of $\GL(\CC^k)$ is isomorphic to  $\Lambda(k)$, and our main result writes $G_M$ as the character of a certain representation of $\GL(\CC^k)$, which we now define.

\begin{defn}
A \emph{diagram} is a finite subset of $\ZZ^2$.
\end{defn}

Given a diagram $D$, let $S_D$ be the group of permutations of $D$. Let $R(D)$ (respectively $C(D)$) be the stabilizer in $S_D$ of the partition of $D$ into rows (respectively columns). The \emph{Young symmetrizer} of $D$ is then $y_D = \sum_{p \in R(D)} \sum_{q \in C(D)} \sgn(q)qp \in \CC[S_D]$.

For a complex vector space $V$, let $V^{\otimes D}$ be the $|D|$-fold tensor product of $V$, except that we think of the tensor factors as labeled by cells in $D$ (coming in some fixed order) rather than $1, 2, \ldots, |D|$. The group $S_D$ acts on $V^{\otimes D}$ on the right, while $\GL(V)$ acts on the left, and these two actions commute.
\begin{defn}
The \emph{Schur module} $V[D]$ associated to $D$ is the left $\GL(V)$-module $V^{\otimes D}y_D$.
\end{defn}
In cases which are understood, the algebraic properties of $V[D]$ tend to reflect interesting combinatorics relating to the diagram $D$, but there is no general combinatorial description of the irreducible decomposition of $V[D]$ or its character. For instance, when $D$ is a skew Young diagram $\lambda\setminus \mu$, the character of $V[D]$ is the skew Schur polynomial $s_{\lambda \setminus \mu}(x_1, \ldots, x_k)$.

\begin{ex} \label{ex:schur-examples}
The \emph{Rothe diagram} of a permutation $w \in S_n$ is $D(w) = \{(i, w(j)) \in [n]^2 : i < j, w(i) > w(j)\}$. It follows from \cite{kraskiewicz, plactification} that the character of $V[D(w)]$ is the \emph{Stanley symmetric function} $F_w(x_1, \ldots, x_k)$ (see \cref{defn:affine-stanley} below).
\end{ex}

Our main result can be viewed as a generalization of \cref{ex:schur-examples} as follows. To each positroid $M \subseteq {[n] \choose k}$, Knutson, Lam, and Speyer \cite{positroidjuggling} associate a certain \emph{affine permutation} $f_M$, i.e. a bijection $\ZZ \to \ZZ$ satisfying the quasi-periodicity property that $f_M(i+n) = f_M(i)+n$ for all $i$. They also prove that $G_M$ is the image in $\Lambda^{n-k}(k)$ of the \emph{affine Stanley symmetric function} $\affF_{f_M}$. Now define the Rothe diagram of $f_M$ as in \cref{ex:schur-examples}, but viewed as a finite subset of the cylinder $\ZZ^2 / \ZZ(n,n)$ (this will cause no difficulties in defining the Schur module $V[D(f_M)]$).

\begin{thm} \label{thm:main}
For any positroid $M \subseteq {[n] \choose k}$, the image of the character of $V[D(f_M)]$ in $\Lambda^{n-k}(k)$ is $G_M$.
\end{thm}
See \cref{rem:truncated-character} for a nicer way to phrase \cref{thm:main}, by slightly modifying the notion of Schur module so that the character naturally lies in $\Lambda^{n-k}(k)$ rather than $\Lambda(k)$. 

Besides being certain intersection numbers for $\Pi_M$, the Schur coefficients of $G_M$ have many other interpretations, and \cref{thm:main} provides an algebraic proof of the nonnegativity of these integers. All of the following can be described as certain Schur coefficients of $G_M$:
\begin{enumerate}[(a)]
\item The 3-point Gromov-Witten invariants for $\Gr(k,n)$;
\item The Schubert coefficients in the product of a Schubert polynomial and a Schur polynomial;
\item The Schur coefficients of the image of an affine Stanley symmetric function in $\Lambda^{n-k}(k)$;
\item The Schur coefficients of the symmetric function $\sum_c Q_{\Des(c)}$, where $Q_D$ is Gessel's fundamental quasisymmetric function and $c$ runs over maximal chains in an interval in Bergeron and Sottile's $k$-Bruhat order.
\end{enumerate}
To elaborate on (a), Postnikov defined certain finite subsets $D$ of the cylinder $\ZZ^2/\ZZ(k,n-k)$ called \emph{toric skew shapes}, and associated to $D$ the \emph{toric Schur polynomial} $s_D(x_1, \ldots, x_k)$, the weight-generating function for semistandard fillings of $D$. He showed that the Schur coefficients of toric Schur polynomials are the 3-point Gromov-Witten invariants for $\Gr(k,n)$, and gave a conjectural representation-theoretic interpretation. 
\begin{conj*}[\cite{postnikov-affine-quantum-schubert}, Conjecture 10.1] For a toric skew shape $D \subseteq \ZZ^2/\ZZ(k,n-k)$, the toric Schur polynomial of $D$ is the character of $V[D]$, where $\dim V = k$. \end{conj*}
We will see (\cref{thm:toric-schur-module}) that Postnikov's conjecture follows as a special case of \cref{thm:main}.

There is an effective recursion for computing the Schur expansion of a Stanley symmetric function $F_w$ based on the so-called \emph{transition formula} of Lascoux and Sch\"utzenberger \cite{lascouxschutzenbergertree}. They construct a tree of permutations with root $w$ such that for any node $v$, $F_v = \sum_{v'} F_{v'}$ where $v'$ runs over children of $v'$, and show that any sufficiently long path from the root leads to a node $v$ such that $F_v$ is a single, easily-described Schur function. We construct a similar tree for the functions $G_M$, providing an effective (although no longer positive) recursion for computing the Schur expansion of $G_M$. The proof of \cref{thm:main} proceeds by constructing a filtration of $V[D(f_M)]$ which, at the level of characters, matches this recursion for $G_M$.

In \cref{sec:background}, we recall some background on affine permutations, and prove basic facts about affine Stanley symmetric functions. In \cref{sec:recurrences}, we prove an analogue of Lascoux-Sch\"utzenberger's transition formula for the symmetric functions $G_M$. \cref{sec:schur} is devoted to Schur modules, and contains the main tools we use to relate the combinatorics of a diagram $D$ to the algebra of $V[D]$. We then apply these tools to Schur modules of affine Rothe diagrams in \cref{sec:main} and prove \cref{thm:main}. Finally, \cref{sec:applications} describes some applications of our results, including a proof of Postnikov's conjecture on toric Schur modules.

\section{Background} \label{sec:background}

\subsection{Affine permutations}

Let $n$ be a positive integer. An \emph{affine permutation of quasi-period $n$} is a bijection $f : \ZZ \to \ZZ$ satisfying $f(i+n) = f(i)+n$ for all $i$. We write $\affS_n$ for the group of all affine permutations. We specify an affine permutation $f$ by the word $f(1), \ldots, f(n)$, since this uniquely determines $f$, writing $\overline{x}$ for $-x$. For instance, $f = 645\overline{1}$ is the affine permutation with $f(1) = 6$, $f(4) = -1$, $f(8) = 3$, and so on.

\begin{defn}
Given $k, m \in \ZZ$, let $\Cyl_{k,m}$ denote the cylinder $\ZZ^2 / \ZZ(k,m)$.
\end{defn}
It is natural to view the graph of $f \in \affS_n$ as a subset of $\Cyl_{n,n}$, namely $\{(i,f(i)) \in \Cyl_{n,n} : i \in \ZZ\}$. For $i \in \ZZ$, let $s_i \in \affS_n$ be the transposition interchanging $i+pn$ and $i+1+pn$ for all $p \in \ZZ$ and fixing all other integers, and let $\tau \in \affS_n$ be the shift map $\tau : i \mapsto i+1$. Let $\affS^0_n := \langle s_0, s_1, \ldots, s_{n-1} \rangle$, and define $\av : \affS_n \to \ZZ$ by $\av(f) = \frac{1}{n}\sum_{i=1}^n (f(i)-i)$.

\begin{prop} \label{prop:av-properties} $\affS_n$ is the semidirect product $\affS_n^0 \rtimes \langle \tau \rangle$, and $\av$ is the projection onto $\langle \tau \rangle \simeq \ZZ$.
\end{prop}

The group $\affS^0_n$ is a Coxeter group (the affine Weyl group of type $\widetilde{A}_n$). By \cref{prop:av-properties}, every $f \in \affS_n$ can be written uniquely as $\tau^j g$ where $g \in \affS^0_n$, and we will implicitly extend many notions of Coxeter combinatorics from $g$ to $f$: the Coxeter length $\ell(g) = \ell(f)$, descents, reduced words, Bruhat order, and so on. The subgroup $\langle s_1, \ldots, s_{n-1} \rangle$ of $\affS_n$ is isomorphic to $S_n$, and we will frequently identify the two.

\begin{defn} \label{defn:bounded}
An affine permutation $f \in \affS_n$ is \emph{bounded} if $i \leq f(i) \leq i+n$ for all $i \in \ZZ$. Let $\Bound(n) \subseteq \affS_n$ denote the subset of bounded permutations, and $\Bound(k,n)$ the set of $f \in \Bound(n)$ such that exactly $k$ of $f(1), \ldots, f(n)$ exceed $n$.
\end{defn}

For instance, $5724 \in \Bound(2,4)$. By \cite[Theorem 3.1]{positroidjuggling}, $\Bound(k,n)$ is in bijection with the rank $k$ positroids on $[n]$.


\subsection{Affine Stanley symmetric functions}

\begin{defn} A \emph{cyclically decreasing affine permutation} is one of the form $f = s_{i_1} \cdots s_{i_k}$ where all entries of the sequence $i_1, \ldots, i_k$ are distinct, and such that if any $j$ and $j+1$ both appear in the sequence, then $j+1$ appears first.
\end{defn}
\begin{ex}
$s_1 s_0 s_3 \in \tilde{S}_4$ is cyclically decreasing, but $s_1 s_3 s_0$ and $s_3 s_0 s_3$ are not.
\end{ex}

A factorization $f = f_1 \cdots f_p$ where $f, f_1, \ldots, f_p \in \affS_n^0$ is \emph{length-additive} if $\ell(f) = \sum_{i=1}^p \ell(f_i)$. 
\begin{defn}[\cite{lam-affine-stanley}] \label{defn:affine-stanley}
The \emph{affine Stanley symmetric function} of $f \in \affS_n$ is the power series
\begin{equation*}
\affF_f = \sum_{(f_1, \ldots, f_p)} x_1^{\ell(f_1)} \cdots x_p^{\ell(f_p)}
\end{equation*}
running over all length-additive factorizations $\tau^{-\av(f)} f = f_1 \cdots f_p$ such that each $f_i$ is cyclically decreasing.
\end{defn}

It is shown in \cite{lam-affine-stanley} that $\affF_f \in \Lambda$. When $f \in \langle s_1, \ldots, s_{n-1} \rangle \simeq S_n$, affine Stanley symmetric functions agree with the symmetric functions introduced by Stanley in \cite{stanleysymm} (except that Stanley's $G_w$ is our $\affF_{w^{-1}}$). Observe that the coefficient of a squarefree monomial in $\affF_f$ is the number of reduced words of $f$. 

For $f \in S_n$, the results of \cite{edelman-greene} imply that $\affF_f$ is Schur-positive, but this need not hold for general affine $f$; for instance, $\affF_{5274} = s_{22} + s_{211} - s_{1111}$. However, it turns out that a predictable subset of the Schur coefficients of $\affF_f$ are nonnegative. Let $\trunc_{k,n-k}$ be the quotient map $\Lambda \to \Lambda^{n-k}(k)$.
\begin{defn}
Given $f \in \affS_n$ and $0 \leq k \leq n$, define $G_{f,k} = \trunc_{k,n-k} \affF_f \in \Lambda^{n-k}(k)$. We usually suppress the dependence on $k$ and simply write $G_f$.
\end{defn}


\begin{thm}[\cite{positroidjuggling}, Theorem 7.1] \label{thm:schur-positive-truncation} If $f \in \Bound(k,n)$, then $G_{f,k} \in \Lambda^{n-k}(k)$ represents the cohomology class of a positroid variety. In particular, $G_{f,k}$ is Schur-positive and nonzero. \end{thm}
Let $T = \langle \tau \rangle$. Since $\affF_f = \affF_{\tau f}$, it holds more generally that $G_{f,k}$ is Schur-positive and nonzero whenever $f \in T \Bound(k,n)$. As we will see, this is a necessary condition.


\begin{defn} \label{defn:rothe} The \emph{Rothe diagram} of $f \in \affS_n$ is the set $D(f) = \{(i,j) \in \Cyl_{n,n} : j < f(i), i < f^{-1}(j)\}$.
\end{defn}
Observe that $D(f)$ has size $\ell(f)$, the number of inversions of $f$. Given \cref{thm:main}, it is no surprise that properties of $\affF_f$ and $G_f$ can be deduced from properties of $D(f)$, as in the next two theorems.


\begin{thm} \label{thm:bounded-diagram-characterization} Let $f \in \affS_n$. Then $f \in T \Bound(k,n)$ if and only if every row of $D(f)$ has at most $n-k$ cells, and every column has at most $k$ cells. \end{thm}

\begin{thm} \label{thm:nonzero-truncation} $G_{f,k} \neq 0$ if and only if $f \in T \Bound(k,n)$. \end{thm}

\section{Recurrences for affine Stanley symmetric functions} \label{sec:recurrences}

Given integers $i < j$ for which $i \not\equiv j \pmod{n}$, let $t_{ij} \in \affS^0_n$ be the transposition interchanging $i+pn$ and $j+pn$ for all $p \in \ZZ$. We use $<$ to denote the strong Bruhat order on $\affS_n$, i.e. the partial order with covering relations $f \lessdot ft_{ij}$ whenever $\ell(ft_{ij}) = \ell(f)+1$. Define sets
\begin{gather*}
B\Phi^+(f,r) = \{ft_{rj} \in \Bound(n) : \text{$r < j$ and $f \lessdot ft_{rj}$}\}\\
B\Phi^-(f,r) = \{ft_{ir} \in \Bound(n) : \text{$i < r$ and $f \lessdot ft_{ir}$}\}.\\
\BCov_r(f) = \{(i,j) \in [n] \times \ZZ : \text{$f \lessdot ft_{ij} \in \Bound(n)$ and $[i,j)$ contains $r$ modulo $n$} \}.
\end{gather*}

Our proof of \cref{thm:main} will be inductive, using two key recursions.
\begin{lem} \label{lem:recursions} For $f \in \Bound(k,n)$ and any $r$, the following two identities hold in $\Lambda^{n-k}(k)$:
\begin{equation*}
s_1 G_f = \sum_{(i,j) \in \BCov_r(f)} G_{ft_{ij}} \quad \text{and} \quad \sum_{g \in B\Phi^-(f,r)} G_{g} = \sum_{g \in B\Phi^+(f,r)} G_{g}.
\end{equation*}
\end{lem}

\begin{proof}
Subtracting the first identity with parameter $r+1$ from the first identity with parameter $r$ gives the second identity. The first identity follows by applying \cref{thm:nonzero-truncation} to a similar formula in \cite{affine-insertion} expressing $s_1 \tilde{F}_f$ as a linear combination of $\tilde{F}_g$.
\end{proof}



The \emph{maximal inversion} of $f \in T\Bound(k,n)$ is the lexicographically maximal pair $(r,s)$ with $1 \leq r < s \leq n$ and $f(r) > f(s)$. If no such pair exists, we say $f$ is \emph{$0$-Grassmannian}.

\begin{defn}
The \emph{bounded affine Lascoux-Sch\"utzenberger (L-S) tree} tree of $f$ is a tree with root $f$ whose vertices are labeled by elements of $\Bound(k,n)$ and whose edges are labeled by $+$ or $-$, defined as follows:
\begin{itemize}
\item If a vertex $g$ is $0$-Grassmannian, then $g$ has no children;
\item If $g$ is not $0$-Grassmannian, then $g$ has children $B\Phi^{-}(ft_{rs}, r)$ (via edges labeled ${+}$) and $B\Phi^{+}(ft_{rs},r) \setminus \{f\}$ (via edges labeled ${-}$).
\end{itemize}
\end{defn}
The maximality of $(r,s)$ implies that $f \lessdot ft_{rs}$, and hence $f \in B\Phi^+(ft_{rs}, r)$. Solving for $G_f$ in the second identity of Lemma~\eqref{lem:recursions} yields the next proposition.

\begin{prop} \label{prop:LS-recurrence}
If $g$ is any non-leaf vertex of a bounded affine L-S tree, then $G_g = \sum_{h^+} G_{h^+} - \sum_{h^-} G_{h^-}$ where $h^+$ and $h^-$ run over the children of $g$ connected by edges labeled ${+}$ and ${-}$ respectively.
\end{prop}

\begin{thm} \label{thm:finite-LS-tree}
The bounded affine L-S tree of any $f \in \Bound(k,n)$ is finite.
\end{thm}

\begin{proof}
One checks that if $g$ is a child of $f$, then either the word $f(1)\cdots f(n)$ has fewer inversions than $g(1)\cdots g(n)$, or they have the same number of inversions and $g(1)\cdots g(n)$ is lexicographically larger than $f(1)\cdots f(n)$.
\end{proof}

If $f \in \Bound(k,n)$ is $0$-Grassmannian, its Rothe diagram $D(f)$ is, after deleting empty rows and columns, a French-style Young diagram of a partition $\lambda(f) \subseteq (n-k)^k$, the \emph{shape} of $f$.
\begin{lem} \label{lem:schur-leaves}
If $f \in \Bound(k,n)$ is $0$-Grassmannian, then $G_f = s_{\lambda(f)}$, which is nonzero in $\Lambda^{n-k}(k)$.
\end{lem}

Given a path $\pi$ in a graph with edges labeled by $\pm$, let $\sgn(\pi)$ be the product of the edge labels. The next theorem follows inductively from \cref{prop:LS-recurrence} and \cref{thm:finite-LS-tree}, using \cref{lem:schur-leaves} as a base case.
\begin{thm} \label{thm:LS-formula}
Given a vertex $g$ of the bounded affine L-S tree of $f \in \Bound(k,n)$, let $\pi_g$ denote the unique path from the root $f$ to $g$. Then $G_f = \sum_g \sgn(\pi_g) s_{\lambda(g)}$, where $g$ runs over the leaves of the tree.
\end{thm}

When $f \in S_n$, the L-S tree has no edges labeled ${-}$, and so \cref{thm:LS-formula} exhibits $G_f = F_f$ as Schur-positive. In the general affine case the Schur-positivity of $G_f$ is not clear from \cref{thm:LS-formula}, but that recurrence is still a much more effective means of computing $G_f$ than the definition in terms of cyclically decreasing factorizations.




\section{Generalized Schur modules} \label{sec:schur}
\begin{defn}
A \emph{cylindric diagram} is a finite subset of a cylinder $\Cyl_{k,m}$. A cylindric diagram $D$ is \emph{toric} if the restriction of the quotient map $\rho : \Cyl_{k,m} \to \ZZ^2/(k\ZZ \times m\ZZ)$ is injective on $D$.
\end{defn}
Observe that a cylindric diagram $D$ has well-defined rows and columns, so one can again associate to $D$ its Young symmetrizer $y_D \in \CC[S_D]$ and Schur modules $V[D]$.

\begin{lem} \label{lem:toric} Let $D$ be a cylindric diagram. If $D$ is not toric, then $V[D] = 0$, while if $D$ is toric, then $V[D] \simeq V[\rho(D)]$. \end{lem}
\cref{lem:toric} implies that all nonzero cylindric Schur modules are in fact ordinary Schur modules, but it will be more natural to work directly with cylindric diagrams.

\begin{defn} Two ordinary diagrams are \emph{equivalent} if they are conjugate under the action of $S_{\ZZ} \times S_{\ZZ}$ on $\ZZ^2$. Equivalent diagrams have the same partitions into rows and columns, and hence isomorphic Schur modules. \end{defn}


The next lemma is a key tool for decomposing Schur modules of diagrams, and all of our technical results depend on it. For simplicity we will state definitions and theorems in this section in terms of ordinary diagrams, but one could just as well phrase them for toric diagrams. Given two ordered pairs $x = (i,j)$ and $x' = (i',j')$, write $x|x' = (i,j')$. For a diagram $D \subseteq \ZZ^2$ and ordered pairs $x = (i,j)$ and $x' = (i',j')$, let $R_x^{x'} D$ be the diagram such that:
\begin{itemize}
\item If $p \notin \{i, i'\}$, then $(p,q) \in R_{x}^{x'} D$ if and only if $(p,q) \in D$;
\item $(i,q) \in R_x^{x'}D$ if and only if $(i,q), (i',q) \in D$;
\item $(i',q) \in R_x^{x'}D$ if and only if $(i,q)$ or $(i',q)$ is in $D$.
\end{itemize}
One checks that $R_x^{x'} D$ has the same size as $D$. Define $C_x^{x'} D$ by modifying columns $j$ and $j'$ analogously. We call the operators $R_x^{x'}$ and $C_x^{x'}$ \emph{James-Peel moves}.


\begin{lem}[\cite{jamespeel}, Theorem 2.4] \label{lem:jp}
Let $D$ be a diagram, and $x, x'$ any two points in $\ZZ^2$. Then $V[C_{x}^{x'}D] \subseteq V[D]$, and there exists a surjective homomorphism $\phi_x^{x'} : V[D] \twoheadrightarrow V[R_{x}^{x'} D]$. If moreover $x, x' \in D$ but $x|x', x'|x \notin D$, then $V[C_{x}^{x'}D] \subseteq \ker \phi_x^{x'}$. In particular, over $\CC$ one concludes in the latter case that $V[R_{x}^{x'} D] \oplus V[C_{x}^{x'}D] \hookrightarrow V[D]$.
\end{lem}


For an ordinary diagram $D \subseteq [k] \times [m]$, let $\square \ast D$ be the union of $D$ with any point not in $[k] \times [m]$ (note that two different choices of point give equivalent diagrams). One can check from the definitions that $\ch V[\square \ast D] = s_1(X_k) \ch V[D]$. The next definition and lemma, which appear in a dual form as \cite[Proposition 3.2]{liubranching}, should be viewed as a generalization of Pieri's rule for computing the Schur expansion of $s_1 s_{\lambda}$.

A subset $\Delta \subseteq \ZZ^2$ is a \emph{transversal} if no two of its points are in the same row or column. For two sets $X, Y \subseteq \ZZ^2$, define $X|Y = \{x|y : x \in X, y \in Y\}$.
\begin{defn} \label{defn:corner}
A \emph{corner configuration} for a diagram $D$ is a pair $(a, \Delta)$ where $\Delta \subseteq \ZZ^2$ is a totally ordered set, $a \in \ZZ^2$, and (a) $\{a\} \cup \Delta$ is a transversal disjoint from $D$; (b) $\{a\} | \Delta$ and $\Delta | \{a\}$ are disjoint from $D$; (c) if $x < y$ are in $\Delta$, then $y|x \in D$.
\end{defn}

\begin{lem} \label{lem:corner-configurations} If $(a, \Delta)$ is a corner configuration for $D$, then $\bigoplus_{x \in \Delta} V[(D \cup a)_{a \to x}] \hookrightarrow V[\square \ast D]$.
\end{lem}

Unfortunately, \cref{lem:corner-configurations} is too weak for our purposes; we will need to consider multiple interacting corner configurations.

\begin{defn} \label{defn:corner-system} A \emph{system of corner configurations} for a diagram $D$ is a finite totally ordered set $\Cor$ of corner configurations such that $\{a : (a, \Delta) \in \Cor\}$ is a transversal, and for all $(a, \Delta_a), (b, \Delta_b) \in \Cor$, one has (a) $\{a\} \cup \Delta_b$ is a transversal; and (b) if $(a, \Delta_a) < (b, \Delta_b)$ and $x \in \Delta_a, y \in \Delta_b$, then $\{b, y\} | \{a, x\}$ intersects $D$.
\end{defn}

\begin{lem} \label{lem:corner-system} Let $\Cor$ be a system of corner configurations for a diagram $D$. Then
\begin{equation*}
\bigoplus_{\substack{(a, \Delta) \in \Cor \\ x \in \Delta}} V[(D \cup a)_{a \to x}] \hookrightarrow V[\square \ast D].
\end{equation*}
\end{lem}

\section{Schur modules of Rothe diagrams} \label{sec:main}
Say $V$ is a $k$-dimensional complex vector space. Recall that the \emph{character} of a complex representation $\rho : \GL(V) \to \GL(U)$ of $\GL(V)$ is the function $\ch(U) : (x_1, \ldots, x_k) \mapsto \tr \rho(\diag(x_1, \ldots, x_k))$, where $\diag(x_1, \ldots, x_k) \in \GL(V)$ is the diagonal matrix with diagonal entries $x_1, \ldots, x_k$, having chosen a basis for $V$. If $U$ is a \emph{polynomial representation}, meaning that upon choosing bases, the entries of the matrices $\rho(g)$ for $g \in \GL(V)$ are polynomials in the entries of $g$, then $\ch(U) \in \Lambda(k)$.

Two polynomial (or rational) representations of $\GL(V)$ are isomorphic if and only if their characters are equal, and the irreducible polynomial representations of $\GL(V)$ have characters $s_{\lambda}(X_k)$ for $\lambda$ such that $\ell(\lambda) \leq k$. This reduces the decomposition of $\GL(V)$-modules to symmetric polynomial calculations. Having fixed $k = \dim V$ and $n$, we let $\trch U = \trunc_{k,n-k} \ch U$ for a $\GL(V)$-module $U$. Call this the \emph{truncated character} of $U$. The next theorem is our main result.
\begin{thm}[Restatement of \cref{thm:main}] \label{thm:main2}
$G_f = \trch V[D(f)]$ for any $f \in \Bound(k,n)$.
\end{thm}

\begin{rem} \label{rem:truncated-character}
We briefly describe a modification of the setting of polynomial representations and Schur modules in which the truncated character operation $\trch$ becomes more natural. Let $T(V)$ be the tensor algebra of $V$. Say a pure tensor $x \in T_d(V) = V^{\otimes d}$ is \emph{$\ell$-symmetric} if its stabilizer under the right action of $S_d$ contains the subgroup of all permutations fixing some $\ell$-subset of $[d]$. Let $I(m) \subseteq T(V)$ be the ideal spanned by all $(m+1)$-symmetric tensors, and define the \emph{truncated Schur module} $V_m[D]$ as the image of $V[D] \subseteq T(V)$ under the quotient map $T(V) \to T(V)/I(m)$. Let $R$ be the Grothendieck group of $\GL(V)$-submodules of $T(V)/I(m)$, made into a ring not by the ordinary tensor product, but using the multiplication in $T(V)/I(m)$. Then $\trch : R \to \Lambda^{m}(k)$ is a ring isomorphism, and a more natural statement of \cref{thm:main2} is that $G_f = \trch V_{n-k}[D(f)]$.
\end{rem}

Our strategy for proving \cref{thm:main2} is to show that $\trch V[D(f)]$ satisfies the recurrences described for $G_f$ in \cref{sec:recurrences}. Namely:

\begin{lem} \label{lem:induction-injection}  If $f \in \Bound(k,n)$ and $r \in \ZZ$, then
\begin{equation*}
\bigoplus_{(i,j) \in \BCov_r(f)} V[D(ft_{ij})] \hookrightarrow V[\square \ast D(f)].
\end{equation*}
\end{lem}
This lemma follows by applying \cref{lem:corner-system} to an appropriate system of corner configurations for $D(f)$; we omit the details.

Let $H_f = \trch V[D(f)]$. Let $\delta : \Lambda^{n-k}(k) \to \ZZ$ be the linear map sending $\bar s_{\lambda}$ to $f^{\lambda^{\vee}}$, the number of standard Young tableaux of shape $\lambda^{\vee} := ([k] \times [n-k]) \setminus \lambda$. (Geometrically, $\delta$ maps the cohomology class of a subvariety to its degree as a projective variety.) To prove $H_f = G_f$, we exploit the fact that that if $F$ is Schur-nonnegative, then $\delta(F) \geq 0$ with equality if and only if $F = 0$. The next lemma can be deduced by two inductions on the order $<_r$, treating the maximal and minimal elements on their own, together with \cref{lem:induction-injection,lem:recursions}.
\begin{lem} \label{lem:H} For any $f \in \Bound(k,n)$, $\delta(H_f) = \delta(G_f)$ and $\sum_{(i,j) \in \BCov_r(f)} H_{ft_{ij}} =  \bar s_1 H_f$.
\end{lem}


Thus, $H_f$ satisfies the recurrences derived for $G_f$ in \cref{sec:recurrences}, and so $H_f = G_f$ will follow if it holds in the base case when $f$ is $0$-Grassmannian, say of shape $\lambda$. But in that case, $G_f = \bar s_{\lambda} = \trch V[\lambda] = H_f$. This proves the main theorem. 
\begin{thm*}For any $f \in \Bound(k,n)$, $G_f = H_f = \trch V[D(f)]$. \end{thm*}





\section{Applications} \label{sec:applications}

\subsection{Toric Schur polynomials} \label{subsec:toric-schur}

A \emph{closed lattice path} $P$ in $\Cyl_{k,n-k}$ is a circular sequence $(p_1, \ldots, p_{n})$ labeled by $\ZZ/n\ZZ$ such that $p_{i+1} - p_i \in \{(\pm 1,0), (0,\pm 1)\}$ for all $i$. If $p_{i+1} - p_i \in \{(1,0), (0,1)\}$ for all $i$, we say $P$ moves from northwest to southeast. We think of $P$ as the path obtained by concatenating the line segments from $p_i$ to $p_{i+1}$ for all $i$.
\begin{defn}
A \emph{cylindric skew shape} is the set of unit squares $[i,i+1] \times [j,j+1]$ in a cylinder $\Cyl_{k,n-k}$ between two closed lattice paths moving from northwest to southeast which do not cross (though they can meet).
\end{defn}
Any cylindric skew shape is a cylindric diagram. A filling of a cylindric skew shape $\Theta$ by positive integers is a \emph{semistandard tableau} if it is weakly increasing rightward across rows, and strictly increasing up columns. As usual, a semistandard tableau is \emph{standard} if it uses exactly the integers $1, 2, \ldots, |\Theta|$.


\begin{defn}[\cite{postnikov-affine-quantum-schubert}]
The \emph{cylindric Schur function} associated to a cylindric skew shape $\Theta$ is the formal power series $s_\Theta := \sum_T x^T$, where $T$ runs over semistandard tableaux of shape $\Theta$.
\end{defn}

If the cylindric skew shape $\Theta \subseteq \Cyl_{k,n-k}$ is a toric diagram, call the polynomial $s_\Theta(X_k)$ a \emph{toric Schur polynomial}. Cylindric Schur functions were introduced by Postnikov \cite{postnikov-affine-quantum-schubert}, and the next theorem summarizes one of his main results.

\begin{thm}[\cite{postnikov-affine-quantum-schubert}]  \label{thm:toric-schur-facts}
If $\Theta \subseteq \Cyl_{k,n-k}$ is a toric skew shape, then $s_{\Theta}(X_k)$ is Schur-positive. Moreover, for $\Theta$ ranging over toric shapes in $\Cyl_{k,n-k}$, the Schur coefficients of $s_\Theta(X_k)$ are exactly the 3-point Gromov-Witten invariants for $\Gr(k,n)$.
\end{thm}
Postnikov conjectured that for any toric skew shape $\Theta$, the toric Schur polynomial $s_\Theta(X_k)$ is the character of the Schur module $V[\Theta]$ \cite[Conjecture 10.1]{postnikov-affine-quantum-schubert}. Lam \cite{lam-affine-stanley} showed that $s_\Theta$ is an affine Stanley symmetric function, and via that connection and \cref{thm:main}, we deduce Postnikov's conjecture.

\begin{thm} \label{thm:toric-schur-module} Let $\Theta \subseteq \Cyl_{k,n-k}$ be a toric diagram. Then $s_\Theta(X_k) = \ch V[\Theta]$. \end{thm}



\subsection{Schubert times Schur coefficients}
Let $\fS_w \in \ZZ[x_1, x_2, \ldots]$ denote the Schubert polynomial associated to $w \in S_{\infty}$, the group of permutations of $\NN$ fixing all but finitely many points. Since Schubert polynomials form a $\ZZ$-basis of $\ZZ[x_1, x_2, \ldots]$, one can write $\fS_u \fS_v = \sum_w c_{u,v}^w \fS_w$ for some integers $c_{u,v}^w$. In fact, $c_{u,v}^w \geq 0$ for geometric reasons, and it is a major open problem in algebraic combinatorics to describe the $c_{u,v}^w$ combinatorially. In this section we given an algebraic interpretation of some of these Schubert structure coefficients.

Given $\lambda \subseteq (n-k)^k$, let $w(\lambda)$ denote the unique $k$-Grassmannian permutation in $S_n$ with Rothe diagram equivalent to $\lambda$. Then $\fS_{w(\lambda)}$ is the Schur polynomial $s_{\lambda}(x_1, \ldots, x_k)$, and so we call the coefficients $c_{u, w(\lambda)}^v$ \emph{Schubert times Schur coefficients}.  If $\lambda \subseteq (n-k)^k$, let $\lambda^{\vee} = ([k] \times [n-k]) \setminus \lambda$. To each pair $u, v$ such that $c_{u, w(\lambda)}^v \neq 0$ for some $\lambda \subseteq (n-k)^k$ (so $u \leq_k v$ are comparable in the \emph{$k$-Bruhat order} $\leq_k$ of \cite{k-bruhat-order}), Knutson-Lam-Speyer \cite{positroidjuggling} associate an affine permutation $f_{u,v} \in \Bound(k,n)$; we omit the details.

\begin{prop} \label{prop:schubert-coefficients}
If $u \leq v$, then $G_{f_{u,v}} = \sum_{\lambda \subseteq (n-k)^k} c_{u, w(\lambda)}^v s_{\lambda^\vee}$.
\end{prop}

\begin{proof}[Proof sketch] It is shown in \cite{positroidjuggling} that the positroid varieties $\Pi_f$ is the image of a Richardson variety (indexed by $u, v$) in the complete flag variety $\Fl(n)$ under the projection $\Fl(n) \to \Gr(k,n)$. The proposition follows by comparing interpretations of $c_{u, w(\lambda)}^v$ and the Schur coefficients of $G_{f_{u,v}}$ as intersection numbers in $\Gr(k,n)$.
\end{proof}



\printbibliography



\end{document}
